﻿// 0912train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 前2个大写字母)（或数字）代表航空公司的缩写，后面4个数字代表航班信息
 按照航空公司的缩写(航班号前2个字母或数字)对所有航班进行排序，
 同一航空公司的航班再按照航班号的后4个数字进行排序最终获得安排好的航班的起飞顺序。
请编写一段代码，根据输入的航班号信息，帮助调度员输出航班的起飞顺序

输入描述
第一行输入航班信息，多个航班号之间用逗号","分隔，输入的航班号不超过100个

输出描述
一行航班信息表示安排好的航班起飞顺序

补充说明
航班号为6位长度，后4位为纯数字，不考虑存在后4位重复的场景
航空公司缩写排序按照从特殊符号$ & *，0~9，A~Z排序

输入
CA3385,CZ6678,SC6508,DU7523,HK4456,MK0987
输出
CA3385,CZ6678,DU7523,HK4456,MK0987,SC6508
 */
class Solution01
{
public:
    static int compareCh(char&ch_1, char&ch_2)
    {
        if (ch_1 == ch_2)return 0;
        //$ & *
        unordered_map<char, int>special_map = {
        	{'$',0},{'&',1},{'*',2}
        };

        bool is_sp_1 = special_map.count(ch_1) > 0;
        bool is_sp_2 = special_map.count(ch_2) > 0;

        if (is_sp_1 && !is_sp_2) return 1;
        if (!is_sp_1 && is_sp_2) return 2;
        if (is_sp_1&&is_sp_2)
        {
            if (special_map.at(ch_1) < special_map.at(ch_2))
                return 1;
            return 2;
        }

        //数字
        bool is_num_1 = isdigit(ch_1), is_num_2 = isdigit(ch_2);
        if (is_num_1 && !is_num_2) return 1;
        if (!is_num_1 && is_num_2) return 2;
        if (is_num_1 && is_num_2)
        {
            int num_1 = ch_1 - '0', num_2 = ch_2 - '0';
            if (num_1 < num_2) return 1;
            return 2;
        }

        //字母
        if (ch_1 < ch_2)return 1;
        return 2;
        //compareCh
    }

    static bool compare(string&str_1, string&str_2)
    {
        int compare_0 = compareCh(str_1[0], str_2[0]);

        if (compare_0 == 0)
        {
            int compare_1 = compareCh(str_1[1], str_2[1]);
            if (compare_1 == 1) return true;
            return false;
        }

        if (compare_0 == 1)
            return true;

        return false;

        //compare
    }

    Solution01(vector<string>&origin_vec)
    {
        //提取前两个字母
        unordered_map <string, vector<pair<string, int>>>kind_map;

        for (auto&str_item:origin_vec)
        {
            string kind = str_item.substr(0, 2);
            string num_str = str_item.substr(2);
            int num = stoi(num_str);

            kind_map[kind].push_back(make_pair(num_str, num));
        }

        //排序类型
        vector<string>sort_kind_v;
        for (auto&map_item:kind_map)
        {
            sort_kind_v.push_back(map_item.first);
        }

        sort(sort_kind_v.begin(), sort_kind_v.end(), compare);

        vector<string>result;
        for (auto&curr_str:sort_kind_v)
        {
            vector<pair<string, int>>child_v = kind_map[curr_str];

            sort(child_v.begin(), child_v.end(), [](pair<string, int>&p_1, pair<string, int>&p_2)
                {
                    return p_1.second < p_2.second;
                });

            for (auto&child_str:child_v)
            {
                string res = curr_str + child_str.first;
                result.push_back(res);
            }
            //for
        }

        for (int i=0; i<result.size(); i++)
        {
            cout << result[i];
            if (i!=result.size()-1)
            {
                cout << ',';
            }
        }
        //Solution01
    }
};


/*
 现在有一个任务数组，数组元素表示在这1s内新增的任务个数，且每秒都有新增任务
 假设 GPU 最多一次执行n个任务，一次执行耗时1s
 在保证 GPU 不空闲的情况下，最少需要多长时间执行完成

输入描述
第一个参数为 GPU 最多执行的任务个数
第二个参数为任务数组的长度
第三个参数为任务数组

输出描述
执行完所有任务需要多少秒

输入
3
5
1 2 3 4 5
输出
6
一次最多执行3个任务
最少耗时6s
 */
class Solution02
{
public:
    Solution02(vector<int>&num_vec,int speed)
    {
        int v_size = num_vec.size();
        int result = 0;
        int i = 0;
        while (i < num_vec.size())
        {
            int num = num_vec[i];
            if (num<= speed)
            {
                result += 1;
                i++;
                continue;
            }

            if (i==v_size-1)
            {
                result += ceil(double(num) / double(speed));
                break;
            }

            //是否满足4的倍数，否则，挪到下一个计算
            int remain = num % speed;
            int curr_time = (num - remain) / speed;
            num_vec[i + 1] += remain;
            result += curr_time;
            i++;
        }
        cout << result;
	    //Solution02
    }
};

class Solution12
{
public:
    Solution12(vector<int>&num_vec, int speed)
    {
        int curr_total = 0;
        int result = 0;
        int v_size = num_vec.size();

        for (int i=0; i<v_size; i++)
        {
            int curr_new = num_vec[i];
            curr_total += curr_new;

            //尝试消耗新增的
            if (speed>= curr_total)
            {
                curr_total = 0;
                result += 1;
            }
            else
            {
                curr_total -= speed;
                result += 1;
            }
        }

        int remain = ceil(double(curr_total) / double(speed));
        result += remain;
        cout << result;
        //Solution12
    }
};

/*
 任何数字位置遇到数字4就直接跳过，其余功能都正常
 */
class Solution03
{
public:
    bool isTarget(int num)
    {
        string num_str = to_string(num);

        for (auto&num_ch:num_str)
        {
            if (num_ch == '4')
                return true;
        }
        return false;
        //isTarget
    }
    Solution03(int num)
    {
        int count = 0;
        for (int i=0; i<=num; i++)
        {
            if (isTarget(i))
                count += 1;
        }
        cout << num - count;
        //Solution03
    }
};


class Solution13
{
public:
    Solution13(string num_str)
    {
        //断开的9进制
        //0-3 0-3
        //5-9 4-8

        //从低位开始处理
        reverse(num_str.begin(), num_str.end());

        int result = 0;
        for (int i=0; i<num_str.size(); i++)
        {
            int curr = num_str[i] - '0';
            if (curr >= 5) curr -= 1;

            result += curr * pow(9, i);
        }

        cout << result;
	    //Solution13
    }
};


/*
一个图像有n个像素点，存储在一个长度为n的数组img里，每个像素点的取值范围[0,255]的正整数。
请你给图像每个像素点值加上一个整数k（可以是负数），
得到新图newImg，使得新图newImg的所有像素平均值最接近中位值128。
请输出这个整数k。
输入描述
n个整数，中间用空格分开
例如
0 0 0 0
4个数值，中间用空格分开
输出描述
一个整数k
补充说明
. 1 <= n <= 100
·如有多个整数k都满足，输出小的那个k；
·新图的像素值会自动截取到[0,255]范围。当新像素值<0，其值会更改为0；当新像素值>255，其值会更改为255;
例如newlmg="-1 -2 256",会自动更改为"0 0 255"
示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
0 0 0 0
输出
128
 */
class Solution04
{
public:
    Solution04(vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        double min_diff = DBL_MAX;
        int result = INT_MIN;

        //如有多个整数k都满足，输出小的那个k
        //cout << 255 - 128; //-127, 128

        for (int i=-127; i<=128; i++)
        {
            double sum = 0;
            for (auto&num:num_vec)
            {
                int curr = num + i;
                curr = max(curr, 0); //小于0取0
                curr = min(curr, 255); //大于255取255
                sum += curr;
            }

            double diff = abs((sum / double(v_size)) - 128);
            if (diff<min_diff)
            {
                min_diff = diff;
                result = i;
            }
        }
        cout << result;
        //Solution04
    }
};


int main()
{
	{
        //cout << 255 - 128; //-127, 128
        vector<int>num_vec;

        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;

        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }

        Solution04 solu(num_vec);

        return 0;
	}
	{
        string num_str;
        cin >> num_str;

        Solution13 solu(num_str);
        return 0;
	}
	{
/*
3
5
1 2 3 4 5

4
5
5 4 1 1 1
*/
        int speed;
        cin >> speed;

        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution12 solu(num_vec, speed);

        return 0;
	}
    
    //string input = "CA3385,CZ6678,SC6508,DU7523,HK4456,MK0987";
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    vector<string>str_vec;
    while (getline(oh_sstream, token, ','))
    {
        str_vec.push_back(token);
    }
    Solution01 solu(str_vec);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
